home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part1 / 8019 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  2.0 KB
  1. Path: anvil.ugrad.cs.ubc.ca!not-for-mail
  2. From: c2a192@ugrad.cs.ubc.ca (Kazimir Kylheku)
  3. Newsgroups: comp.lang.c
  4. Subject: Re: merge algorithm
  5. Date: 28 Feb 1996 15:52:49 -0800
  6. Organization: Computer Science, University of B.C., Vancouver, B.C., Canada
  7. Message-ID: <4h2pshINN47q@anvil.ugrad.cs.ubc.ca>
  8. References: <312CEE69.842@onyx.idbsu.edu> <4gljrl$auj@sun001.spd.dsccc.com> <825461208snz@genesis.demon.co.uk>
  9. NNTP-Posting-Host: anvil.ugrad.cs.ubc.ca
  10.  
  11. In article <825461208snz@genesis.demon.co.uk>,
  12. Lawrence Kirby  <fred@genesis.demon.co.uk> wrote:
  13.  >In article <4gljrl$auj@sun001.spd.dsccc.com>
  14.  >           jmccarty@spd.dsccc.com "Mike McCarty" writes:
  15.  >
  16.  >>In article <312CEE69.842@onyx.idbsu.edu>,
  17.  >>Joe E. Coffland <jcofflan@onyx.idbsu.edu> wrote:
  18.  >>)I am trying to find an algorithm to merge two sorted arrays containing
  19.  >>)n elements.
  20.  >>)ie. A[1] <= A[2]<= ... <= A[m] and A[m+1] <= A[m+2] <= ... <A[n]
  21.  >>)The algorithm must run in O(n) time and require only a small amount of
  22.  >>)fixed additional memory regardless of the size of m or n. I have reason
  23.  >>)to believe that there is such an algorithm but I have only been able to
  24.  >>)find algorithms that meet the memory restriction but run in at best
  25.  >>)O(nlogn) and are recursive (which can through some work of course be
  26.  >>)changed in to an iterative algorithm). If any one can point me to a book
  27.  >>)or any other source of information on the subject or just get me headed
  28.  >>)in the right direction it would be greatly appriciated.
  29.  >
  30.  >As far as I am aware there is no such algorithm although I'd be very
  31.  >happy to be proved wrong. One obvious O(nlogn) algorithm is heapsort.
  32.  
  33. It seems that way, but it's hard to ignore the fact that merging two sorted
  34. arrays given enough additional memory is an O(n) operation, which suggests
  35. that some clever (yet inexpensive) rearrangement of the input may be conducive
  36. to a a solution better than O(nlogn). Things are not always as they seem.
  37. One has to only consider the cleverness of the Fast Fourier Transform.
  38. -- 
  39.  
  40.